#ifndef SORT_MERGE_HPP
#define SORT_MERGE_HPP

#include "../common.hpp"

YFWZ100_NS_BEGIN

template <typename PointerLike>
static inline
void merge_sorted(PointerLike a, size_t mid, size_t length)
{
  size_t i = 0, j = mid;
  while (j < length) {
    while (i < j && a[i] < a[j]) {
      i++;
    }
    if (i < j) {
      auto t = a[j];
      for (int k = j; k > i; k--) {
        a[k] = a[k - 1];
      }
      a[i] = t;
      i++;
      j++;
    } else {
      break;
    }
  }
}

template <typename PointerLike>
void merge_sort(PointerLike a, size_t length)
{
  size_t mid = length / 2;
  if (length > 1) {
    merge_sort(a, mid);
    merge_sort(a + mid, length - mid);
  }
  merge_sorted(a, mid, length);
}

YFWZ100_NS_END

#endif//SORT_MERGE_HPP
